#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include "santas-tour.h"

// COMPILE: gcc -o st -lm santas-tour.c

/*
typedef struct _node {
  double x, y;
  int number;
  // (# of nodes within distance radius)/(radius**2*M_PI)
  double density; 
  double density_radius;
  // which "bucket" does this node go into?
  double grey_value;
  struct _node *prev, *next;
} node;
*/

typedef struct _grid_hash_item {
    double x, y;
    int number;
    // (# of nodes within distance radius)/(radius**2*M_PI)
    double density; 
    double density_radius;
    // which "bucket" does this node go into?
    double grey_value;
    struct _grid_hash_item *next;
} grid_hash_item;    

//------------------------------------------------------------------------------

void partition_into_regions(node *list, int *n_regions, node *regions);
// void find_paths(node *sorted_on_x, node *sorted_on_y, node **path1, node **path2);
node *read_nodes(char *filename);
int check_solution(node *master_list, node *path1, node *path2);
void write_solution(char *filename, node *path1, node *path2);

//------------------------------------------------------------------------------

void partition_into_regions(node *list, int *n_regions, node *regions)
{
    return;
}

//------------------------------------------------------------------------------

// void find_paths(node *sorted_on_x, node *sorted_on_y, node **path1, node **path2)
// {
//     return;
// }

//------------------------------------------------------------------------------

node *read_nodes(char *filename)
{
    FILE *fin = fopen(filename, "r");
    node *list_head = NULL, *curr_node = NULL, *prev_node = NULL;
    int number;
    char junk[256];
    double x, y;
    if (NULL == fin) {
        fprintf(stderr, "Unable to open %s\n", filename);
        exit(0);
    }
    fgets(junk, 255, fin);  // skip header
    while (!feof(fin)) {
        if (fscanf(fin, "%d,%lf,%lf", &number, &x, &y) < 3) {
            fclose(fin);
            break;
        }
        if (NULL == (curr_node = (node *) malloc(sizeof(node)))) {
            fprintf(stderr, "Memory overflow\n");
            fclose(fin);
            exit(0);
        }
        curr_node->prev = prev_node;        
        if (NULL == prev_node) {
            list_head = curr_node;
        } else {            
            prev_node->next = curr_node;
        }
        curr_node->prev = prev_node;
        curr_node->next = NULL;
        curr_node->x = x;
        curr_node->y = y;
        curr_node->number = number;
        curr_node->density = 0.0;
        curr_node->density_radius = 0.0;
        curr_node->grey_value = 0.0; 
        prev_node = curr_node;        
    }
    fclose(fin);
    return list_head;
}

//------------------------------------------------------------------------------

void print_nodes(node *list)
{
    node *nd;
    printf("number   |xy                  |dens  |rad   |grey  \n");
    printf("---------------------------------------------------\n");
    for (nd = list; NULL != nd; nd = nd->next) {
        printf("%7d  |", nd->number);
        printf("%8.2lf, %8.2lf  |", nd->x, nd->y);
        printf("%4.2lf  |", nd->density);
        printf("%4.2lf  |", nd->density_radius);        
        printf("%4.2lf  \n",  nd->grey_value);
    }    
}

//------------------------------------------------------------------------------

void write_solution(char *filename, node *path1, node *path2)
{
    FILE *fout = fopen(filename, "w");
    node *nd1, *nd2;
    if (NULL == fout) {
        fprintf(stderr, "Unable to open %s\n", filename);
        return;
    }    
    fprintf(fout, "path1,path2\n");
    for (nd1 = path1, nd2 = path2; nd1 != NULL && nd2 != NULL;
    nd1 = nd1->next, nd2 = nd2->next) {
        fprintf(fout, "%d,%d\n", nd1->number, nd2->number);
    }
    fclose(fout);    
}

//------------------------------------------------------------------------------

// void read_solution

//------------------------------------------------------------------------------

int check_solution(node *master_list, node *path1, node *path2)
{
    return 0;
}

//------------------------------------------------------------------------------

int compare_b_nodesy( const void *a, const void *b );

int compare_b_nodesx( const void *a, const void *b )
{
    const basic_node *ba = (const basic_node *)a;
    const basic_node *bb = (const basic_node *)b;

    int retval = (ba->x > bb->x) - (ba->x < bb->x);

    return  (0 == retval) ? compare_b_nodesy( a, b ) : retval;  // Bad if dup. nodes.
}

int compare_b_nodesy( const void *a, const void *b )
{
    const basic_node *ba = (const basic_node *)a;
    const basic_node *bb = (const basic_node *)b;

    int retval = (ba->y > bb->y) - (ba->y < bb->y);

    return  (0 == retval) ? compare_b_nodesx( a, b ) : retval;  // Bad if dup. nodes.
}

int full_node_count( node* list )
{
    static int n_cnt;
    static node *lst;

    if( list == NULL )  return  0;

    // Memoize just ONE list.
    if( lst == list )  return  n_cnt;
      else if( lst != NULL )  return  0;

    node *n = list;
    int c = 1;
    for( ; n->next != NULL; c++ )  n = n->next;

    n_cnt = c;
    lst   = list;

    return  n_cnt;
}

int copy_nodes_for_sort( node* list, basic_node** b_list )
{
    if( NULL == list )
    {
        *b_list = NULL;
        return  0;
    }

    int size = full_node_count( list );
    basic_node *nodes;

    if( NULL == (nodes = (basic_node *)malloc( sizeof(basic_node)*size )) ) 
    {
        fprintf( stderr, "Memory overflow in copy_nodes_for_sort\n" );
        exit(0);
    }

    *b_list = nodes;

    node       *n = list;
    basic_node *b = nodes;

    while( 1 )
    {
        b->x = n->x;
        b->y = n->y;
        b->number = n->number;
//        printf( "X: %8.2lf  Y: %8.2lf\n", b->x, b->y );
        b++;

        if( n->next == NULL )  break;
        n = n->next;
    }

    return  size;
}

basic_node *sortx( node *list )
{
    basic_node *b_nodes;
    int size = copy_nodes_for_sort( list, &b_nodes );

    qsort( b_nodes, size, sizeof(basic_node), (int(*)(const void*, const void*))compare_b_nodesx );

    int c = 0, lastix = size -1;
    for( ; c<lastix; c++ )  b_nodes[c].next = b_nodes+(c+1);  // Set next based on sort order.
    b_nodes[c].next = NULL;

    return  b_nodes;
}

basic_node *sorty( node *list )
{
    basic_node *b_nodes;
    int size = copy_nodes_for_sort( list, &b_nodes );

    qsort( b_nodes, size, sizeof(basic_node), (int(*)(const void*, const void*))compare_b_nodesy );

    int c = 0, lastix = size -1;
    for( ; c<lastix; c++ )  b_nodes[c].next = b_nodes+(c+1);  // Set next based on sort order.
    b_nodes[c].next = NULL;

    return  b_nodes;
}

//------------------------------------------------------------------------------

int main(int argc, char **argv)
{
    node       *list;
    if ( (argc != 2) && (argc != 3) ) {
        fprintf(stderr, "usage %s <csvfile>\n", argv[0]);
        return 0;
    }

    if( NULL != (list = read_nodes(argv[1])) )
    {
        if( argc == 2 )
        {
            print_nodes(list);

        } else if( argc == 3 )
          {
              basic_node *sortedx, *sortedy;
              sortedx = sortx( list );
              sortedy = sorty( list );
              node *path1, *path2;
              find_paths( sortedx, sortedy, &path1, &path2 );
          }
    }

    return 0;
}


